package LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class LC_399_EvaluateDivision {

    public static void main(String[] args) {

    }

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            int length = equations.length;
            HashMap<String, ArrayList<String>> neighbors = new HashMap<>();
            HashMap<String, ArrayList<Double>> neighborsValue = new HashMap<>();
            for (int i = 0; i < length; i++) {
                if (!neighbors.containsKey(equations[i][0])) {
                    neighbors.put(equations[i][0], new ArrayList<>());
                    neighborsValue.put(equations[i][0], new ArrayList<>());
                }
                if (!neighbors.containsKey(equations[i][1])) {
                    neighbors.put(equations[i][1], new ArrayList<>());
                    neighborsValue.put(equations[i][1], new ArrayList<>());
                }
                neighbors.get(equations[i][0]).add(equations[i][1]);
                neighborsValue.get(equations[i][0]).add(values[i]);
                neighbors.get(equations[i][1]).add(equations[i][0]);
                neighborsValue.get(equations[i][1]).add(1 / values[i]);
            }

            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                String a = queries[i][0];
                String b = queries[i][1];
                res[i] = dfs(1.0, a, b, neighbors, neighborsValue, new HashSet<>());
                if (res[i] == 0.0) res[i] = -1.0;
            }
            return res;
        }

        double dfs(double value, String a, String b, HashMap<String, ArrayList<String>> neighbors, HashMap<String, ArrayList<Double>> neighborsValue, HashSet<String> hashSet) {
            if (hashSet.contains(a)) return 0.0;
            if (!neighbors.containsKey(a)) return 0.0;
            if (a.equals(b)) return value;
            hashSet.add(a);
            List<String> neigh = neighbors.get(a);
            List<Double> neighValues = neighborsValue.get(a);
            double tmp = 0.0;
            for (int i = 0; i < neigh.size(); i++) {
                String dot = neigh.get(i);
                double dotValue = neighValues.get(i);
                tmp = dfs(value * dotValue, dot, b, neighbors, neighborsValue, hashSet);
                if (tmp != 0.0) break;
            }
            hashSet.remove(a);
            return tmp;
        }

    }
}